package study;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CourseTable {

    List<List<Integer>> edgeList;
    int[] visited;
    int[] result;
    boolean valid = true;
    int index;

    public int[] courseTable(int numCourses, int[][] prerequisites) {
        edgeList = new ArrayList<>();
        visited = new int[numCourses];
        result = new int[numCourses];
        for (int i = 0; i < numCourses; ++i) {
            edgeList.add(new ArrayList<>());
        }
        index = numCourses - 1;
        for (int[] info : prerequisites) {
            edgeList.get(info[1]).add(info[0]);
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        if (!valid) {
            return new int[0];
        }
        return result;
    }

    public void dfs(int u) {
        visited[u] = 1;
        for (int v : edgeList.get(u)) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
        result[index--] = u;
    }

    public static void main(String[] args) {
        CourseTable courseTable = new CourseTable();
        int[][] input = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        int numCourses = 4;
        int[] ret2 = courseTable.courseTable(numCourses, input);
        System.out.println(Arrays.toString(ret2));
    }

}
